package com.jonlandrum.selfbalancingtree.redblacktree;

import static org.hamcrest.CoreMatchers.instanceOf;
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertThat;
import static org.junit.Assert.assertTrue;

import org.junit.After;
import org.junit.Before;
import org.junit.Test;

import com.jonlandrum.selfbalancingtree.Node;

public class RedBlackTreeTest {
    private RedBlackTree<String> tree;
    
    @Before
    public void init() {
        tree = new RedBlackTree<String>();
    }
    
    @After
    public void destroy() {
        tree = null;
    }
    
    @Test
    public void testConstructorNull() {
        assertThat(tree, instanceOf(RedBlackTree.class));
    }
    
    @Test
    public void testConstructorString() {
        tree = new RedBlackTree<String>("Root");
        assertThat(tree, instanceOf(RedBlackTree.class));
    }
    
    @Test
    public void testConstructorNode() {
        tree = new RedBlackTree<String>(new Node<String>("Root"));
        assertThat(tree, instanceOf(RedBlackTree.class));
    }
    
    @Test
    public void testAddElement() {
        Node<String> node1 = new Node<String>("Root");
        Node<String> node2 = new Node<String>("String");
        Node<String> node3 = new Node<String>("Type");
        Node<String> node4 = new Node<String>("Unicycle");
        Node<String> node5 = new Node<String>("Ubiquitous");
        tree.addElement(node1);
        int left = tree.getRoot().getLeftChild().getBlackHeight();
        int right = tree.getRoot().getRightChild().getBlackHeight();
        assertTrue(left == right);
        assertTrue(tree.getRoot().getColor() == 1);
        tree.addElement(node2);
        left = tree.getRoot().getLeftChild().getBlackHeight();
        right = tree.getRoot().getRightChild().getBlackHeight();
        assertTrue(left == right);
        assertEquals(node1, tree.getRoot());
        assertEquals(node2, tree.getRoot().getRightChild());
        assertTrue(tree.getRoot().getColor() == 1);
        assertTrue(tree.getRoot().getRightChild().getColor() == 0);
        tree.addElement(node3);
        left = tree.getRoot().getLeftChild().getBlackHeight();
        right = tree.getRoot().getRightChild().getBlackHeight();
        assertTrue(left == right);
        assertEquals(node2, tree.getRoot());
        assertEquals(node1, tree.getRoot().getLeftChild());
        assertEquals(node3, tree.getRoot().getRightChild());
        assertEquals(1, tree.getRoot().getColor());
        assertEquals(0, tree.getRoot().getLeftChild().getColor());
        assertEquals(0, tree.getRoot().getRightChild().getColor());
        tree.addElement(node4);
        left = tree.getRoot().getLeftChild().getBlackHeight();
        right = tree.getRoot().getRightChild().getBlackHeight();
        assertTrue(left == right);
        assertEquals(node2, tree.getRoot());
        assertEquals(node1, tree.getRoot().getLeftChild());
        assertEquals(node3, tree.getRoot().getRightChild());
        assertEquals(node4, tree.getRoot().getRightChild().getRightChild());
        assertEquals(1, tree.getRoot().getColor());
        assertEquals(1, tree.getRoot().getLeftChild().getColor());
        assertEquals(1, tree.getRoot().getRightChild().getColor());
        assertEquals(0, tree.getRoot().getRightChild().getRightChild().getColor());
        tree.addElement(node5);
        left = tree.getRoot().getLeftChild().getBlackHeight();
        right = tree.getRoot().getRightChild().getBlackHeight();
        assertTrue(left == right);
        assertEquals(node2, tree.getRoot());
        assertEquals(node1, tree.getRoot().getLeftChild());
        assertEquals(node5, tree.getRoot().getRightChild());
        assertEquals(node3, tree.getRoot().getRightChild().getLeftChild());
        assertEquals(node4, tree.getRoot().getRightChild().getRightChild());
        assertEquals(1, tree.getRoot().getColor());
        assertEquals(1, tree.getRoot().getLeftChild().getColor());
        assertEquals(1, tree.getRoot().getRightChild().getColor());
        assertEquals(0, tree.getRoot().getRightChild().getLeftChild().getColor());
        assertEquals(0, tree.getRoot().getRightChild().getRightChild().getColor());
        tree = new RedBlackTree<String>();
        tree.addElement(node5);
        tree.addElement(node4);
        tree.addElement(node3);
        tree.addElement(node2);
        tree.addElement(node1);
        left = tree.getRoot().getLeftChild().getBlackHeight();
        right = tree.getRoot().getRightChild().getBlackHeight();
        assertTrue(left == right);
        assertEquals(node5, tree.getRoot());
        assertEquals(node2, tree.getRoot().getLeftChild());
        assertEquals(node4, tree.getRoot().getRightChild());
        assertEquals(node1, tree.getRoot().getLeftChild().getLeftChild());
        assertEquals(node3, tree.getRoot().getLeftChild().getRightChild());
        assertEquals(1, tree.getRoot().getColor());
        assertEquals(1, tree.getRoot().getLeftChild().getColor());
        assertEquals(1, tree.getRoot().getRightChild().getColor());
        assertEquals(0, tree.getRoot().getLeftChild().getLeftChild().getColor());
        assertEquals(0, tree.getRoot().getLeftChild().getRightChild().getColor());
    }
}